https://introtcs.org/public/lec_03_computation.html

개요

The main takeaways from this chapter are:

• We can use logical operations such as AND, OR, and NOT to compute an output from an input (see Section 3.2).

• A Boolean circuit is a way to compose the basic logical operations to compute a more complex function (see Section 3.3). We can think of Boolean circuits as both a mathematical model (which is based on directed acyclic graphs) as well as physical devices we can construct in the real world in a variety of ways, including not just silicon-based semi-conductors but also mechanical and even biological mechanisms (see Section 3.5).

• We can describe Boolean circuits also as straight-line programs, which are programs that do not have any looping constructs (i.e., no while / for/ do .. until etc.), see Section 3.4.

• It is possible to implement the AND, OR, and NOT operations using the NAND operation (as well as vice versa). This means that circuits with AND/OR/NOT gates can compute the same functions (i.e., are equivalent in power) to circuits with NAND gates, and we can use either model to describe computation based on our convenience, see Section 3.6. To give out a “spoiler”, we will see in Chapter 4 that such circuits can compute all finite functions.

One “big idea” of this chapter is the notion of equivalence between models (Big Idea 3). Two computational models are equivalent if they can compute the same set of functions. Boolean circuits with AND/OR/NOT gates are equivalent to circuits with NAND gates, but this is just one example of the more general phenomenon that we will see many times in this book.

이번 장에서는 다음과 같은 내용을 공부한다고 한다.

• 논리 연산 AND, OR, NOT을 사용해 입력에 대해 출력을 내놓는 방법.
• 부울 회로란 기본적인 논리 연산을 조합해 복잡한 함수를 만드는 것이다.
• 부울 회로를 straight-line 프로그램(반복문이 없는 코드)으로 작성한다.
• AND, OR, NOT을 조합해 NAND를 만들 수 있고 반대로도 할 수 있다.

Defining Computation

"알고리즘"이란?
informal : An algorithm is a set of instructions for how to compute an output from an input by following a sequence of "elementary steps".
An algorithm $A$ computes a function $F$ if for every input x, if we follow the instructions of A on the input $x$, we obtain the output $F(x)$.
정해진 방법과 순서대로 단계들을 밟아가면서 입력된 값에 따라 출력값을 내놓는 일련의 지침들이다.

AND, OR, NOT

OR(a,b) :

• 0 : a=b=0 일 때
• 1 : 나머지 경우
  AND(a,b) :
• 1 : a=b=1 일 때
• 0 : 나머지 경우
  NOT(a) :
• 1 : a = 0
• 0 : a = 1

a && (b || c) = (a && b) || (a && c) 일까?
참을 양수, 거짓을 0으로 하고 AND는 * OR는 + 라고 해보자.
수학에서 분배의 법칙에 따라 a*(b+c) = ab + ac가 된다.

XOR

XOR(a,b) : a+b mod 2

• 0 : a 와 b 모두 참이거나, 모두 거짓일 때
• 1: 하나가 참이고 하나가 거짓일 때

XOR를 AND, OR, NOT으로 구현하려면?
w1 = AND(a,b)
w2 = NOT(w1)
w3 = OR(a,b)
AND(w2,w3)